﻿using System;
using System.Collections.Generic;
using Library.Collections.Generic;
using Library.Collections.Specialized;
using INDEX = System.UInt64;

namespace Library.Linq
{
    public static class BestFirst
    {
        static bool To<T>(IStack<T> stack, IEnumerable<T> path)
        {
            INDEX n = 0;

            using (var e1 = stack.GetEnumerator(Direction.Reverse))
            {
                using (var e2 = path.GetEnumerator())
                {
                    while (e1.MoveNext() & e2.MoveNext())
                    {
                        if (object.ReferenceEquals(e1.Current, e2.Current)) n++;
                        else break;
                    }
                }
            }

            while (stack.Count > n)
            {
                if (!stack.Pop()) return false;
            }
            return path.Skip(n).All(item => stack.Push(item));
        }

        public static IEnumerable<IEnumerable<TNode>> AsEnumerable<TNode, TKey>(TNode tree, Func<IEnumerable<TNode>, TKey> keySelector)
            where TNode : ITreeReadOnly<TNode>
        {
            return AsEnumerable(tree, new PriorityQueueCaching<IEnumerable<TNode>, TKey>(keySelector), new Library.Collections.Generic.Stack<TNode>());
        }

        public static IEnumerable<IEnumerable<TNode>> AsEnumerable<TNode, TKey>(TNode tree, Func<IEnumerable<TNode>, TKey> keySelector, IComparer<TKey> comparer)
            where TNode : ITreeReadOnly<TNode>
        {
            return AsEnumerable(tree, new PriorityQueueCaching<IEnumerable<TNode>, TKey>(keySelector, comparer), new Library.Collections.Generic.Stack<TNode>());
        }

        public static IEnumerable<IEnumerable<TNode>> AsEnumerable<TNode>(TNode tree, IQueue<IEnumerable<TNode>> queue)
            where TNode : ITreeReadOnly<TNode>
        {
            return AsEnumerable(tree, queue, new Library.Collections.Generic.Stack<TNode>());
        }

        public static IEnumerable<IEnumerable<TNode>> AsEnumerable<TNode, TKey>(TNode tree, Func<IEnumerable<TNode>, TKey> keySelector, IStack<TNode> stack)
            where TNode : ITreeReadOnly<TNode>
        {
            return AsEnumerable(tree, new PriorityQueueCaching<IEnumerable<TNode>, TKey>(keySelector), stack);
        }

        public static IEnumerable<IEnumerable<TNode>> AsEnumerable<TNode, TKey>(TNode tree, Func<IEnumerable<TNode>, TKey> keySelector, IComparer<TKey> comparer, IStack<TNode> stack)
            where TNode : ITreeReadOnly<TNode>
        {
            return AsEnumerable(tree, new PriorityQueueCaching<IEnumerable<TNode>, TKey>(keySelector, comparer), stack);
        }

        public static IEnumerable<IEnumerable<TNode>> AsEnumerable<TNode>(TNode tree, IQueue<IEnumerable<TNode>> queue, IStack<TNode> stack)
            where TNode : ITreeReadOnly<TNode>
        {
            IStack<TNode> _stack = (IStack<TNode>)stack.Clone(Direction.Reverse, Access.Read);
            IEnumerable<TNode> path;
            TNode root = tree;
            TNode node;

            try
            {
                if (!stack.Push(tree)) yield break;
                queue.Enqueue((IEnumerable<TNode>)stack.Clone(Direction.Reverse, Access.Read));

                while (queue.Dequeue(out path))
                {
                    if (To(stack, path))
                    {
                        yield return path;

                        if (!stack.Peek(out node)) continue;

                        foreach (var child in node.Children)
                        {
                            if (stack.Push(child))
                            {
                                queue.Enqueue((IEnumerable<TNode>)stack.Clone(Direction.Reverse, Access.Read));
                                stack.Pop();
                            }
                        }
                    }
                }
            }
            finally
            {
                To(stack, _stack);
            }
        }
    }
}
